/* file cube.c  */
/* by   Shawn C. Dodd, Feb 2003 */
/* use  Brute force a wooden cube puzzle. */


#include <stdio.h>
#include <time.h>


/* An individual block in the puzzle. */
struct block
{
	int kink;			/* whether the string goes straight through (0) or kinks to the right (1) */
	int twist;			/* number of 90-degree twists of the current block with respect to previous (0-3) */
};

/* A point in 3D space occupied by a block. */
struct point
{
	int x;
	int y;
	int z;
};

/* The array of blocks comprising the puzzle.  With kink initializers. */
#define LEN 27
struct block blocks[LEN] = {
	{0,0}, {0,0}, {1,0},  {1,0}, {1,0}, {0,0},  {1,0}, {1,0}, {0,0},
	{1,0}, {1,0}, {1,0},  {0,0}, {1,0}, {0,0},  {1,0}, {1,0}, {1,0},
	{1,0}, {0,0}, {1,0},  {0,0}, {1,0}, {0,0},  {1,0}, {0,0}, {0,0}
};

/* An array of indexes into the block array indicating where the kinks are. */
#define KINKLEN 16
const int kinks[KINKLEN] = {2,3,4,6,7,9,10,11,13,15,16,17,18,20,22,24};

/* How close to the origin do all blocks need to be in order to qualify
as a potential solution? */
#define PROX 2

#define SKIP 10000

void plotBlocks( void (*funcBefore)(void), void (*funcNode)(struct point*), void (*funcAfter)(void) );

/* globals */
long long trials = 0;
long candidates = 0;
long notInRange = 0;
long notProximate = 0;
long collisions = 0;
int highWater = KINKLEN;
time_t start, last;
int spanCount = 0;
double bestFit = 100.0;

/* The unit vectors. */
const struct point units[6] = {
	{1,0,0},
	{0,1,0},
	{0,0,1},
	{-1,0,0},
	{0,-1,0},
	{0,0,-1}
};

/* There are only 24 rotations, so I precomputed them. */
const int rotations[6][4] = {
	{2,1,5,4},
	{0,2,3,5},
	{1,0,4,3},
	{5,4,2,1},
	{3,5,0,2},
	{4,3,1,0}
};

/* Output-related functions below. */

void listKinks( void )
{
	int i;
	for( i=0; i<LEN; i++ )
	{
		printf("%s ", (blocks[i].kink ? "K" : "s"));
	}
	printf("\n");
}

void listTwists( void ) {
	int i;
	for( i=0; i<KINKLEN; i++ )
	{
		printf("%d ", blocks[kinks[i]].twist);
	}
}

void printMark( int m ) { printf("%d\ttrials=%lld\n", m, trials); }

void noopNode( struct point *p ) { ; }

void noop( void ) { ; }

void printBefore( void ) { ; }

void printAfter( void ) { printf("\n"); }

void printNode( struct point *p )
{
	printf("(%d, %d, %d) ", p->x, p->y, p->z);
}

void reportSummary( void )
{
	time_t elapse;
	last = time(&last);

	printf("Total Trials:    \t%lld\nTotal Candidates:\t%ld\n", trials, candidates);
	printf("Not in Range:    \t%ld\nNot Proximate:   \t%ld\n", notInRange, notProximate);
	printf("Collisions:      \t%ld\n", collisions);
	printf("Candidate Threshold: \t%ld\n", PROX);
	printf("High Water Mark: \t%d\n", highWater);
	elapse = last - start;
	printf("Total Running Time: \t%ld:%.2ld (mm:ss)\n", elapse/60, elapse%60);
	printf("Run Rate (trial/s): \t%.0f\n", (float)trials/(float)elapse);
}

/* Analysis-related functions below. */

int proximate( struct point *p )
{
	return ( abs(p->x) <= PROX && abs(p->y) <= PROX && abs(p->z) <= PROX );
}

int inRange( struct point *p )
{
	return ( p->x>=0 && p->y>=0 && p->z>=0 );
}

int collides( int index, struct point *location, struct point points[] )
{
	for( ; index>=0; index-- )
	{
		if( (location->x == points[index].x) && (location->y == points[index].y) && (location->z == points[index].z) )
			return 1;
	}
	return 0;
}

void analyseShape( struct point location )
{
	if( proximate(&location) )
	{
		spanCount++;
	}
}

void showCandidate( struct point points[], int length )
{
	int i;
	for( i=0; i<length; i++ )
	{
		printf("(%d, %d, %d) ", points[i].x, points[i].y, points[i].z );
		if( (i+1)%3==0 ) printf("\n");
	}
}

void showCandidateCStyle( struct point points[], int length )
{
	printf("{ ");
	int i;
	for( i=0; i<length; i++ )
	{
		printf("{%d, %d, %d}", points[i].x, points[i].y, points[i].z );
		if( (i+1)<length ) printf(", ");
	}
	printf(" },\n");
}

void showCandidatePretty( struct point points[], int length )
{
	printf("After %lld trials:\n", trials);
	showCandidate( points, length );
	listTwists(); printf("\n");
}

void updateTimeStats( void )
{
	/* TODO  I think this is broken; it gives funny readings */
	long diff = 0;
	long now;
/*	now = getsometime();  */
    if( now == 0 )
    	perror("Error: Unable to get time of day");
    diff = now - last;
	printf("%ld\tticks per %ld trials, %.3f\ttics per trial\r", diff, SKIP, (float)diff/(float)SKIP);
	last = now;
}

int randTwist( void ) 
{ 
	return (rand()%4); 
}

/*
Scramble the blocks giving random twists to each block.
*/
void scrambleBlocks( void ) 
{
	int k;

	srand(time(0));
	for( k=0; k<KINKLEN; k++ )
	{
		blocks[kinks[k]].twist = randTwist();
	}
	printf("Random start: ");
	listTwists(); printf("\n");
}

/*
Compute the new orientation of the given block, based on its kink
and the given orientation; translate the given location based on this
new orientation.
*/
void follow( struct block *bl, struct point *location, int *orientation )
{
	struct point vector;

	/* transform the orientation based on the block's twist and kink */
	if( bl->kink )
	{
		/* the block is kinked, so we must apply a rotation to the orientation vector */
		*orientation = rotations[*orientation][bl->twist];
	}

	/* translate the location based on the orientation vector */
	vector = units[*orientation];
	location->x += vector.x;
	location->y += vector.y;
	location->z += vector.z;
}

/*
Walk the chain of blocks, plotting their position in space, invoking the
given function for each block position.
*/
void plotBlocks( void (*funcBefore)(void), void (*funcNode)(struct point*), void (*funcAfter)(void) )
{
	/* setup */
	int i;
	int orientation = 0;				/* orientation of the current block as index into array of unit vectors */
	int candidate = 1, traceCandidate = 0;
	int _notInRange=0, _notProximate=0, _collides=0;
	static struct point points[LEN];
	struct point location = {0, 0, 0};

	trials++;
	funcBefore();

	/* walk the blocks */
	for( i=0; i<LEN; i++ )
	{
		funcNode(&location);
		points[i] = location;
#ifdef DEBUG		
		/* for debugging */
		if( trials % 1590728L == 0 || trials <200 )
		{
			traceCandidate = 1;
			candidate = 0;
			follow(&blocks[i], &location, &orientation);
			continue;
		}
#endif
		if( !inRange(&location) ) { _notInRange=1; candidate=0; return; }
		if( !proximate(&location) ) { _notProximate=1; candidate=0; return; }
		if( i>2 )
			if( collides(i-1, &location, points) ) { _collides=1; candidate=0; return; }
		follow(&blocks[i], &location, &orientation);
	}

	funcAfter();

/*	if( hasMiddle(blocks) ) candidate=1; */

	if( candidate )
	{
		candidates++;
		showCandidatePretty( points, LEN );
	}

	if( traceCandidate )
	{
		showCandidateCStyle( points, LEN );
	}

	/* update stats */
	if( _notInRange ) notInRange++;
	if( _notProximate ) notProximate++;
	if( _collides ) collisions++;

}

void getPartArgs( int argc, char* argv[], int parts[] )
{
	int c = 1;
	int i;
	if( argc < 2 ) return;
	for( i=0; i<4; i++ ) parts[i] = 0;
	while( c < argc ) 
	{
		switch( argv[c][0] ) 
		{
			case '1':
				parts[0] = 1;
				break;
			case '2':
				parts[1] = 1;
				break;
			case '3':
				parts[2] = 1;
				break;
			case '4':
				parts[3] = 1;
				break;
		}
		c++;
	}
}

/*
Check for flag that says we should randomize blocks, return true/false.
*/
int randFlagArgs( int argc, char* argv[] )
{
	int c = 1;
	while( c < argc ) 
	{
		if( argv[c][0] == '-' && argv[c][1] == 'r' && argv[c][2] == 0 )
			return 1;
		c++;
	}
	return 0;
}

/*
Check for -pX argument for partition mode.
*/
int pmodeArgs( int argc, char* argv[] )
{
	int p = -1, c = 1;
	while( c < argc )
	{
		if( argv[c][0] == '-' && argv[c][1] == 'p' && argv[c][2] != 0 )
		{
			return (argv[c][2] - '1');
		}
		c++;
	}
	return p;
}

/*
Recurse over the blocks, twisting each kinked block, plotting each
block's position.
*/
void twistAndShout( int depth )
{
	int i;

	if( depth==KINKLEN ) return;
	for( i=0; i<(depth>=KINKLEN-1?3:4); i++ )
	{
		twistAndShout(depth+1);
		blocks[kinks[depth]].twist = (blocks[kinks[depth]].twist + 1) % 4;
		plotBlocks( noop, noopNode, noop );
		if( depth < highWater ) { highWater=depth; }
	}
}

void twistAndShout_pmode( int partition ) 
{
	printf("Partition  %d: ", partition );
	blocks[kinks[0]].twist = partition;
	listTwists(); printf("\n");
	twistAndShout(1);
	plotBlocks( noop, noopNode, noop );
}


/* ------------------------------------------------------------------------ */

int main( int argc, char* argv[] )
{
	/* setup */
	start = time( &start );
	last = start;
	int partitions[] = {1,1,1,1};
	int pmode;
	printf("Started.\n");

	/* retrieve arguments */
	if( randFlagArgs( argc, argv ) ) scrambleBlocks();
	pmode = pmodeArgs( argc, argv ); 
	
	/* find the cube shape */
	if( -1 != pmode ) 
		twistAndShout_pmode( pmode );
	else
		twistAndShout(0); 

	/* report results */
	reportSummary();

	return 0;
}

